Routing is the process of selecting network communication paths in a network for transmitting data packets using Open System Interconnection (“OSI”) layer three. Routing directs packet forwarding from a source node to a destination node through one or more intermediate nodes. Intermediate nodes may include computers, routers, bridges, gateways, and switches. The routing process relies on routing tables that maintain a record of routes to various network destinations. Thus, maintaining routing tables that have the correct routing information is pivotal for efficient routing.
Routing tables typically include a variety of information, such as the addresses of local sub-networks, port identifiers, addresses of adjacent nodes, static routes, and dynamically learned routes, among other routing information. The routing information is used to determine a particular intermediate node representing the next hop on the path to the final destination node. Each intermediate node that receives the packet checks the destination address of the packet, looks up routing information in the routing table, determines a next hop using the information in the routing table and determines which port to use to forward the data packet to the next hop.
Hence, if hundreds of intermediate nodes are used to transmit a packet from a source to a destination, then hundreds of routing tables have to be consulted. It takes time for a routing algorithm to look-up information in a routing table and to determine an optimal route to the destination node. Each time a routing algorithm for an intermediate node performs these operations, a delay in the transmission of the packet occurs. Additionally, these delays increase depending on the number of metrics used to determine the optimal path to the destination node, such as bandwidth requirements, path cost, load, reliability, hop count, etc.
Moreover, routing tables have to be constantly updated, as when one of the nodes is experiencing a failure, the nodes that used that node as their next hop will have to discard those entries from the routing table, and create new routing information. The newly created information is then passed to all adjacent nodes, which then repeat the process and pass the information to their corresponding adjacent nodes. Eventually all the nodes in the network receive the updated information and proceed to discover new paths to the destination node that do not include the failed node. For a network with N routers, a fully meshed network topology update can generate on the order of N2 (squared) calculations. This phenomenon, referred to as the N-squared problem, severely degrades network performance and scalability. By way of example, establishing dedicated connections between 20 nodes requires 400 connections, which takes a significant amount of computation time.
Currently, cloud-based wide area network provisioning encompasses establishing and provisioning as many broadband links on a peer-to-peer basis as there are cloud accesses between a tenant and cloud servers. This generates an N-squared problem due to the full-meshing between tenants to multiple clouds which is expensive and slow to establish, producing higher costs, reduced scalability and higher time to market (“TTM”).